#include <cstdio>
#include <cstring>
#include <queue>
const int N = 5010;
int n, m, heads[N], cnt;
struct Edge {
	int v, nxt, c;
} e[300010];
inline void add(int u, int v, int c) {
	e[++cnt].c = c, e[cnt].nxt = heads[u], e[cnt].v = v, heads[u] = cnt;
}
std::queue< int > q;
bool vis[N];
int dis[N], tot[N];
bool spfa() {
	q.push(0);
	vis[0] = true;
	memset(dis, 0x3f, sizeof(dis));
	dis[0] = 0;
	++tot[0];
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		vis[x] = false;
		for (int i = heads[x]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (dis[v] > dis[x] + e[i].c) {
				dis[v] = dis[x] + e[i].c;
				++tot[v];
				if (tot[v] > n) return true;
				if (!vis[v]) {
					q.push(v);
					vis[v] = true;
				}
			}
		}
	}
	return false;
}
int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
	freopen("FiniteDiff.in", "r", stdin);
	freopen("FiniteDiff.out", "w", stdout);
#endif
#endif

	scanf("%d%d", &n, &m);
	int c, cc, y;
	for (int i = 1; i <= n; ++i) { add(0, i, 0); }
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &c, &cc, &y);
		add(cc, c, y);
	}
	if (spfa())
		printf("NO");
	else {
		for (int i = 1; i <= n; ++i) { printf("%d ", dis[i]); }
	}
	return 0;
}